Сверхтьюринговые вычисления
Сверхтьюринговыми вычислениями (или гипервычислениями (англ. hypercomputation)) называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах[англ.], а также некоторые другие типы вычислений — например, интерактивные вычисления[источник не указан 3170 дней]. Термин гипервычисления (англ. hypercomputation) был впервые введён Джеком Коуплендом и Дианой Праудфут.[1] Возможность физической реализации таких вычислений активно обсуждается.
История
[править | править код]Модели, более мощные, чем машина Тьюринга, были введены Аланом Тьюрингом в его работе 1939 года «Системы логик, основанных на ординалах». Эта работа исследовала математические системы, в которых существовал оракул, который мог вычислить одну произвольную нерекурсивную функцию на множестве натуральных чисел. Он использовал эту модель для того, чтобы показать, что даже в такой, более мощной системе, всё равно присутствуют невычислимые функции (например, проблема остановки машины с оракулом). В своей работе Тьюринг ясно дал понять, что такая модель является не более чем математической абстракцией и не может быть реализована в реальном мире.[2]
Предполагаемые способы сверхтьюринговых вычислений
[править | править код]- Машина Тьюринга, которая может выполнить бесконечное количество шагов за конечное время (просто возможность работы машины Тьюринга в течение бесконечного времени (то есть потенциальная бесконечность) недостаточна). Один из предполагаемых способов достичь такого результата — использовать замедление времени для того, чтобы позволить компьютеру совершить бесконечное количество циклов за конечное по часам внешнего наблюдателя время (такое вычисление потребует бесконечной энергии — см. пространство-время Маламета — Хогарта). Ещё одним, чисто математическим, способом является так называемая машина Зенона, основанная на парадоксе Зенона. Машина Зенона выполняет свой первый шаг вычислений за время, например, 1 минуту, следующий за ½ минуты, третий за ¼ минуты и т. д. Суммируя эту бесконечную геометрическую прогрессию, мы получим, что машина выполняет бесконечное количество шагов в течение 2 минут. Однако, в соответствии с рассуждениями аналогичными классическому парадоксу Зенона, такая машина невозможна не только физически, но и логически.[3]
- Вечная машина Тьюринга это обобщение машины Зенона, которая может выполнить неопределенно продолжительное вычисление, шаги в котором перенумерованы потенциально трансфинитными ординальными числами. Она моделирует обычную во всех остальных смыслах машину Тьюринга, для которой неостанавливающиеся вычисления завершаются путём достижения специального состояния, зарезервированного для достижения предельного ординала, и для которой доступны результаты всех предыдущих бесконечных вычислений.[4]
- Действительный компьютер (подвид идеализированного аналогового компьютера) может быть способен осуществлять гипервычисления[5] при условии, что физика допускает существование настоящих действительных чисел. Это, вероятно, требует существования каких-то очень странных законов физики (например наличия измеримой физической константы, которая может быть использована в качестве оракула — см., например, константа Хайтина) и должно, как минимум, требовать возможности измерения физических констант с произвольной точностью, несмотря на тепловой шум и квантовомеханические эффекты.
- Квантовомеханические системы, которые каким-то образом используют, например, бесконечную суперпозицию состояний для вычисления невычислимых функций.[6] Это невозможно при использовании стандартного квантового компьютера, поскольку доказано, что обычный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство).[7]
- Техника, известная как неограниченный детерминизм, может позволять вычисление невычислимых функций. Это вопрос является предметом обсуждения в литературе.
- Использование замкнутых времениподобных кривых, вопреки распространённому мнению, не позволяет выполнять сверхтьюринговые вычисления, так как отсутствует бесконечный объём памяти.
- В начале 1990-х годов Хава Сигельманн[8] предложила модель, основанную на бесконечной эволюции нейронных сетей, способную проводить гипервычисления.[9]
- В предположениях непрерывной Ньютоновой вселенной (когда время и пространство бесконечно делимы), существует возможность построить цепочку вычислительных модулей , каждый из которых в 2 раза меньше и в 2 раза быстрее предыдущего[10]. При этом нет нужды прибегать к неограниченным массам, силам, скоростям, поскольку меньший размер очевидно предполагает более быструю вычислительную способность при фиксированной физической скорости процесса, . Машина обладает бесконечной памятью даже если каждый модуль обладает только конечной памятью, так как модулей бесконечно много. Кроме того, машина способна совершить бесконечное число операций за конечное время, подобно машине Зенона, так как операции следующего модуля выполняются за в 2 раза меньшее время, чем предыдущего, и мы получаем сходящуюся геометрическую прогрессию временных интервалов. Существенное отличие машины Зенона и машины в том, что не может оперировать с выделенной конечной ячейкой памяти бесконечное число раз за конечное время. Это освобождает от так называемого парадокса Томсона[11], суть которого в непредсказуемости финального результата выполнения бесконечной последовательности записи поочередно 0,1,0,1,... в фиксированную ячейку памяти. Тем не менее, даже если классический парадокс Томсона в такой машине не допускается, его "инвертированная" версия гипотетически может быть реализована[12].
См. также
[править | править код]Примечания
[править | править код]- ↑ Alan Turing’s forgotten ideas in computer science Архивная копия от 11 ноября 2013 на Wayback Machine. Scientific American, April 1999.
- ↑ «Предположим, что мы получили какой-то способ решения проблем теории чисел, оракул, дающий решения таких задач. Мы не должны дальше углубляться в вопрос природы оракула, за исключением того, что он не может быть машиной.»(Undecidable p. 167, a reprint of Turing’s paper Systems of Logic Based On Ordinals)
- ↑ См. например Shagrir, O. Super-tasks, accelerating Turing machines and uncomputability (англ.) // Theor. Comput. Sci. 317, 1-3 : journal. — 2004. — June (vol. 317). — P. 105—114. — doi:10.1016/j.tcs.2003.12.007. Архивировано 21 июля 2011 года.
- ↑ Джоэл Девид Хемкинс и Энди Льюис, Infinite time Turing machines Архивировано 5 октября 2011 года., Journal of Symbolic Logic, 65(2):567—604, 2000.
- ↑ Арнольд Шёнхаге, «On the power of random access machines», in Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP), pages 520—529, 1979. Source of citation: Scott Aaronson, «NP-complete Problems and Physical Reality» Архивная копия от 15 января 2010 на Wayback Machine p. 12
- ↑ Существуют утверждения в пользу этого; смотри например Tien Kieu. Quantum Algorithm for the Hilbert's Tenth Problem (англ.) // Int. J. Theor. Phys.[англ.] : journal. — 2003. — Vol. 42. — P. 1461—1478. — doi:10.1023/A:1025780028846. и процитированную там литературу. Ошибки подхода Kieu были указаны Warren D. Smith в Three counterexamples refuting Kieu’s plan for «quantum adiabatic hypercomputation»; and some uncomputable quantum mechanical tasks Архивная копия от 6 марта 2010 на Wayback Machine
- ↑ Bernstein and Vazirani, Quantum complexity theory Архивная копия от 11 марта 2016 на Wayback Machine, SIAM Journal on Computing, 26(5):1411—1473, 1997.
- ↑ : BINDS lab : HAVA’S BIO : Дата обращения: 7 июня 2011. Архивировано 4 октября 2011 года.
- ↑ Verifying Properties of Neural Networks Архивная копия от 4 марта 2016 на Wayback Machine p.6
- ↑ E. B. Davies, Building infinite machines, The British Journal for the Philosophy of Science, 52:671-682, 2001.
- ↑ J. Thomson, Tasks and Super-Tasks, Analysis, 15:1-13, 1954.
- ↑ A. Kutsenko, Programming infinite machines, Erkenntnis, 87:181-189, 2022.
Литература
[править | править код]- Martin Davis, Why there is no such discipline as hypercomputation, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 4-7, Special Issue on Hypercomputation
- Mike Stannett, The case for hypercomputation Архивная копия от 4 марта 2016 на Wayback Machine, Applied Mathematics and Computation, Volume 178, Issue 1, 1 July 2006, Pages 8-24, Special Issue on Hypercomputation
- Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
- Hava Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
- Hava Siegelmann. The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461—472.
- Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
- L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real numbers instead of bits.
- On the computational power of neural nets (недоступная ссылка)
- Toby Ord. Hypercomputation: Computing more than the Turing machine can compute: A survey article on various forms of hypercomputation.
- Apostolos Syropoulos (2008), Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer. ISBN 978-0-387-30886-9
- Burgin, M. S. (1983) Inductive Turing Machines, Notices of the Academy of Sciences of the USSR, v. 270, No. 6, pp. 1289—1293
- Mark Burgin (2005), Super-recursive algorithms, Monographs in computer science, Springer. ISBN 0-387-95569-0
- Cockshott, P. and Michaelson, G. Are there new Models of Computation? Reply to Wegner and Eberbach, The computer Journal, 2007
- Copeland, J. (2002) Hypercomputation, Minds and machines, v. 12, pp. 461—502
- Martin Davis (2006), «The Church-Turing Thesis: Consensus and opposition». Proceedings, Computability in Europe 2006. Lecture notes in computer science, 3988 pp. 125—132
- Hagar, A. and Korolev, A. (2007) Quantum Hypercomputation — Hype or Computation? http://philsci-archive.pitt.edu/archive/00003180/
- Rogers, H. (1987) Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge Massachusetts